package homework;

public class HomeWork45 {
    public void sortColors(int[] nums) {
        sort(nums,0,nums.length-1);
    }

    private void sort(int[] nums,int start, int length) {
        if(start>length){
            return ;
        }
        int k=sap(nums,start,length);
        sort(nums,start,k-1);
        sort(nums,k+1,length);
    }

    private int sap(int[] nums, int low, int high) {
        int tmp=nums[low];
        while (low<high) {
            while (low<high&&tmp<=nums[high]){
                high--;
            }
            if(low<high){
                nums[low]=nums[high];
                low++;
            }
            while (low<high&&nums[low]<=tmp){
                low++;
            }
            if(low<high){
                nums[high]=nums[low];
                high--;
            }
        }
        nums[low]=tmp;
        return low;
    }
//public static int[] quickSort1 (int[] arr) {
//    partition1 (arr, 0, arr.length - 1);
//    return arr;
//}
//
//    static void partition1(int arr [], int left, int right) {
//        if (left > right) {
//            return;
//        }
//        int pivot = arr [left];
//        int i = left, j = right;
//        while (i < j) {
//            while (i < j && arr [j] >= pivot) {
//                j--;
//            }
//            if (i < j) {
//                arr [i] = arr [j];
//                i++;
//            }
//            while (i < j && arr [i] <= pivot) {
//                i++;
//            }
//            if (i < j) {
//                arr [j] = arr [i];
//                j--;
//            }
//        }
//        arr [i] = pivot;
//        partition1 (arr, left, i - 1);
//        partition1 (arr, i + 1, right);
//    }

    public static void main(String[] args) {
//        HomeWork45.quickSort1(new int[]{2,0,2,1,1,0});
        HomeWork45 homeWork45=new HomeWork45();
        homeWork45.sortColors(new int[]{2,0,2,1,1,0});
    }
}
